home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / ingres04.lzh / source / decomp / aggregate.c < prev    next >
Encoding:
C/C++ Source or Header  |  1985-02-08  |  14.9 KB  |  701 lines
  1. # include    <ingres.h>
  2. # include    <tree.h>
  3. # include    <symbol.h>
  4. # include    "globs.h"
  5. # include    <sccs.h>
  6. # include    <errors.h>
  7.  
  8. SCCSID(@(#)aggregate.c    8.3    2/8/85)
  9.  
  10.  
  11.  
  12.  
  13. /*
  14. **    AGGREGATE - replace aggregates with their values
  15. **
  16. **    Aggregate attempts to optimize aggregate processing
  17. **    wherever possible. It replaces aggregates with their
  18. **    values, and links aggregate functions which have
  19. **    identical by-lists together.
  20. **
  21. **    Note that for the sake of this code, A "prime"
  22. **    aggregate is one in which duplicates are removed.
  23. **    These are COUNTU, SUMU, and AVGU.
  24. **
  25. **    Aggregate first forms a list of all aggregates in
  26. **    the order they should be processed.
  27. **
  28. **    For each aggregate, it looks at all other aggregates
  29. **    to see if there are two simple aggregates
  30. **    or if there is another aggregate funtion with the
  31. **    same by-list.
  32. **
  33. **    An attempt is made to run
  34. **    as many aggregates as possible at once. This can be
  35. **    done only if two or more aggregates have the same
  36. **    qualifications and in the case of aggregate functions,
  37. **    they must have identical by-lists.
  38. **    Even then, certain combinations
  39. **    of aggregates cannot occure together. The list is
  40. **    itemized later in the code.
  41. **
  42. **    Aggregate calls BYEVAL or AGEVAL to actually process
  43. **    aggregate functions or aggregates respectively.
  44. **
  45. **    Trace Flags:
  46. **        40
  47. */
  48.  
  49. aggregate(root)
  50. QTREE    *root;
  51. {
  52.     struct agglist    alist[MAXAGG + 1];
  53.     QTREE        *rlist[MAXAGG + 1];
  54.     struct agglist    *al, *al1;
  55.     register QTREE    *agg, *aop1, *r;
  56.     QTREE        *aop, *agg1;
  57.     int        i, simple_agg, varmap;
  58.     int        attcnt, anyagg, attoff, twidth;
  59.     QTREE        *makavar(), *agspace();
  60.     extern char    *rangename();
  61.     extern QTREE    *ageval();
  62.     extern QTREE    *byeval();
  63.  
  64.     al = alist;
  65.     De.de_aggnext = al;
  66.     De.de_agglim = &al[MAXAGG];
  67.  
  68.     findagg(&root, root);    /* generate list of all aggregates */
  69.     De.de_aggnext->agpoint = 0;    /* mark end of the list */
  70.     anyagg = 0;
  71.  
  72.     varmap = root->sym.value.sym_root.lvarm | root->sym.value.sym_root.rvarm;
  73.  
  74.     /* process each aggregate */
  75.     for (;agg = al->agpoint; al++)
  76.     {
  77.         /* is this still an aggregate? */
  78.         if (agg->sym.type != AGHEAD)
  79.             continue;
  80.         mapvar(agg, 0);    /* map the aggregate tree */
  81.         anyagg++;
  82.  
  83.         De.de_sourcevar = bitpos(agg->sym.value.sym_root.lvarm | agg->sym.value.sym_root.rvarm);
  84. #        ifdef xDTR1
  85.         if (tTf(40, 4))
  86.             printf("De.de_sourcevar=%d,rel=%s\n", De.de_sourcevar, rangename(De.de_sourcevar));
  87. #        endif
  88.  
  89.         simple_agg = (agg->left->sym.type == AOP);    /* TRUE if no bylist */
  90.         aop = agg->left;    /* assume it was TRUE */
  91. #        ifdef xDTR1
  92.         if (tTf(40, 0))
  93.             printf("%s\n", simple_agg ? "agg" : "agg-func");
  94. #        endif
  95.         if (simple_agg)
  96.         {
  97.             /* simple aggregate */
  98.             rlist[0] = agspace(aop);
  99.             twidth = aop->sym.value.sym_op.opfrml & I1MASK;    /* init width to the width of the aggregate */
  100.         }
  101.         else
  102.         {
  103.             attoff = agg->left->left->sym.value.sym_resdom.resno + 2;
  104.             aop = aop->right;    /* find the AOP node */
  105.             /* assign  new source variable for aggregate */
  106.             al->agvarno = getrange(&varmap);
  107.             /* compute width of bylist + count field */
  108.             twidth = findwid(agg->left) + 4;
  109.  
  110.             /* make sure the aggregate does not exceed max dimensions */
  111.             if (chkwidth(aop, &twidth, attoff))
  112.                 derror(AGFTOBIG);
  113.         }
  114.         attcnt = 1;    /* one aggregate so far */
  115.  
  116.         /* look for another identical aggregate */
  117.         for (al1 = al + 1; agg1 = al1->agpoint; al1++)
  118.         {
  119.  
  120.             /* if agg is nested inside agg1 then ignore it */
  121.             if (al->agfather == agg1 || agg1->sym.type != AGHEAD)
  122.             {
  123.                 continue;
  124.             }
  125.  
  126.             /* split aggs and agg-func apart */
  127.             /* check for identical aggregate */
  128.             if (simple_agg)
  129.             {
  130.                 aop1 = agg1->left;    /* find AOP node */
  131.  
  132.                 if (aop1->sym.type != AOP)
  133.                     continue;    /* not a simple agg */
  134.  
  135.                 /* make sure they can be run together */
  136.                 if (checkagg(agg, aop, agg1, aop1) == 0) 
  137.                     continue;
  138.  
  139.                 if ((i = sameagg(agg, aop1, attcnt)) >= 0)
  140.                 {
  141.                     /* found identical aggregate to rlist[i] */
  142.                     r = rlist[i];
  143.                 }
  144.                 else
  145.                 {
  146.                     /* put this agg in with the others */
  147.  
  148.                     /* first make sure it won't exceed tuple length */
  149.                     if (chkwidth(aop1, &twidth, 0))
  150.                         continue;    /* can't be included */
  151.                     r = rlist[attcnt++] = agspace(aop1);
  152.  
  153.                     /* connect into tree */
  154.                     aop1->left = agg->left;
  155.                     agg->left = aop1;
  156.                 }
  157.             }
  158.             else
  159.             {
  160.                 /* aggregate function */
  161.                 if (!sameafcn(agg->left->left, agg1->left->left))
  162.                     continue;
  163.  
  164.                 aop1 = agg1->left->right;    /* find AOP */
  165.  
  166.  
  167.                 if (checkagg(agg, aop, agg1, aop1) == 0)
  168.                 {
  169.                     /* same by-lists but they can't be run together */
  170.                     continue;
  171.                 }
  172.  
  173.                 if ((i = sameagg(agg, aop1, attcnt)) < 0)
  174.                 {
  175.                     /* make sure there is room */
  176.                     if (chkwidth(aop1, &twidth, attcnt + attoff))
  177.                         continue;
  178.  
  179.                     /* add aggregate into tree */
  180.                     i = attcnt++;
  181.  
  182.                     aop1->left = agg->left->right;
  183.                     agg->left->right = aop1;
  184.                 }
  185.  
  186.                 r = makavar(aop1, al->agvarno, i + attoff);
  187.             }
  188.             /* replace aggregate in original tree with its value */
  189.             *(al1->father) = r;
  190.  
  191.             /* remove aggregate from local list */
  192.             agg1->sym.type = -1;
  193. #            ifdef xDTR1
  194.             if (tTf(40, 3))
  195.                 printf("including aghead %x\n", agg1);
  196. #            endif
  197.         }
  198.  
  199.         /* process aggregate */
  200.         if (simple_agg)
  201.         {
  202.             rlist[attcnt] = 0;
  203.             ageval(agg, rlist);    /* pass tree and result list */
  204.             r = rlist[0];
  205.         }
  206.         else
  207.         {
  208.             opt_bylist(alist, agg);
  209.             byeval(al->agfather, agg, al->agvarno);
  210.             r = makavar(aop, al->agvarno, attoff);
  211.         }
  212.         /*
  213.         ** Link result into tree. al->father hold the address
  214.         ** &(tree->left) or &(tree->right).
  215.         */
  216.         *(al->father) = r;
  217. #        ifdef xDTR1
  218.         if (tTf(40, 4))
  219.         {
  220.             printf("agg value\n");
  221.             treepr(*(al->father));
  222.         }
  223. #        endif
  224.     }
  225.     if (anyagg)
  226.     {
  227.         opt_bylist(alist, root);
  228.         mapvar(root, 0);    /* remap main tree */
  229.     }
  230. }
  231. /*
  232. **    findagg builds a list of all aggregates
  233. **    in the tree. It finds them by leftmost
  234. **    innermost first.
  235. **
  236. **    The parameters represent:
  237. **        nodep:    the address of the node pointing to you
  238. **                eg. &(tree->left) or &(tree->right)
  239. **        agf:    the root node. or if we are inside
  240. **            a nested aggregate, the AGHEAD node
  241. */
  242.  
  243. findagg(nodep,  agf)
  244. QTREE    **nodep;
  245. QTREE    *agf;
  246. {
  247.     register QTREE        *q, *f;
  248.     register struct agglist    *list;
  249.     int            agg;
  250.  
  251.     if ((q = *nodep) == NULL)
  252.         return;
  253.  
  254.     f = agf;
  255.     if (agg = (q->sym.type == AGHEAD))
  256.         f = q;    /* this aggregate is now the father root */
  257.  
  258.     /* find all aggregates below */
  259.     findagg(&(q->left), f);
  260.     findagg(&(q->right), f);
  261.  
  262.     /* if this is an aggregate, put it on the list */
  263.     if (agg)
  264.     {
  265.         if (De.de_aggnext >= De.de_agglim)
  266.             derror(TOOMANYAGGS);
  267.         list = De.de_aggnext;
  268.         list->father = nodep;
  269.         list->agpoint = q;
  270.         list->agfather = agf;
  271.         De.de_aggnext++;
  272.     }
  273. }
  274. /*
  275. **    Agspace allocates space for the result of
  276. **    a simple aggregate.
  277. */
  278.  
  279. QTREE *
  280. agspace(aop)
  281. QTREE    *aop;
  282. {
  283.     register QTREE    *a, *r;
  284.     register int    length;
  285.     extern char    *need();
  286.  
  287.     a = aop;
  288.     length = a->sym.value.sym_op.opfrml & I1MASK;
  289.     r = (QTREE *) need(De.de_qbuf, length + QT_HDR_SIZ);
  290.     r->left = r->right = 0;
  291.     r->sym.type = a->sym.value.sym_op.opfrmt;
  292.     r->sym.len = length;
  293.  
  294.     return (r);
  295. }
  296. /*
  297. ** Chkwidth -- make sure that the inclusion of another aggregate will
  298. **    not exceed the system limit. This means that the total width
  299. **    cannot exceed MAXTUP and the number of domains cannot exceed MAXDOM-1
  300. */
  301.  
  302. chkwidth(aop, widthp, domno)
  303. QTREE    *aop;
  304. int    *widthp;
  305. int    domno;
  306. {
  307.     register int    width;
  308.  
  309.     width = *widthp;
  310.  
  311. #    ifdef xDTR1
  312.     if (tTf(40, 10))
  313.         printf("agg width %d,dom %d\n", width, domno);
  314. #    endif
  315.  
  316.     width += (aop->sym.value.sym_op.opfrml & I1MASK);
  317.  
  318.     if (width > MAXTUP || domno > MAXDOM - 1)
  319.         return (1);
  320.  
  321.     *widthp = width;
  322.     return (0);
  323. }
  324. /*
  325. **    Determine whether an aggregate is prime
  326. **    or a don't care aggregate. Returns TRUE
  327. **    if COUNTU,SUMU,AVGU,MIN,MAX,ANY.
  328. **    Returns false if COUNT,SUM,AVG.
  329. */
  330.  
  331. cprime(aop)
  332. QTREE    *aop;
  333. {
  334.     register int    i;
  335.  
  336.     i = TRUE;
  337.     switch (aop->sym.value.sym_op.opno)
  338.     {
  339.       case opCOUNT:
  340.       case opSUM:
  341.       case opAVG:
  342.         i = FALSE;
  343.     }
  344.     return (i);
  345. }
  346. /*
  347. **    Getrange find a free slot in the range table
  348. **    for an aggregate function.
  349. **
  350. **    If there are no free slots,derror is called
  351. */
  352.  
  353. getrange(varmap)
  354. int    *varmap;
  355. {
  356.     register int    i, map, bit;
  357.  
  358.     map = *varmap;
  359.  
  360.     for (i = 0; i < MAXRANGE; i++)
  361.     {
  362.         /* if slot is used, continue */
  363.         if ((bit = 1 << i) & map)
  364.             continue;
  365.  
  366.         map |= bit;    /* "or" bit into the map */
  367.         *varmap = map;
  368.  
  369. #        ifdef xDTR1
  370.         if (tTf(40, 10))
  371.             printf("Assn var %d, map %o\n", i, map);
  372. #        endif
  373.  
  374.         return (i);
  375.     }
  376.     derror(NODESCAG);
  377.     return  (-1);
  378. }
  379.  
  380.  
  381. checkagg(aghead1, aop1, aghead2, aop2)
  382. QTREE    *aghead1;
  383. QTREE    *aop1;
  384. QTREE    *aghead2;
  385. QTREE    *aop2;
  386. {
  387.     register QTREE    *aop_1, *aop_2, *agg1;
  388.     int        ok;
  389.  
  390.     /* two aggregate functions can be run together
  391.     ** according to the following table:
  392.     **
  393.     **        prime    !prime    don't care
  394.     **
  395.     ** prime    afcn?    never    afcn?
  396.     ** !prime    never    always    always
  397.     ** don't care    afcn?    always    always
  398.     **
  399.     ** don't care includes: ANY, MIN, MAX
  400.     ** afcn? means only if a-fcn's are identical
  401.     */
  402.  
  403.     aop_1 = aop1;
  404.     aop_2 = aop2;
  405.     agg1 = aghead1;
  406.  
  407.     if (!prime(aop_1) && !prime(aop_2))
  408.         ok = TRUE;
  409.     else
  410.         if (sameafcn(aop_1->right, aop_2->right))
  411.             ok = cprime(aop_1) && cprime(aop_2);
  412.         else
  413.             ok = FALSE;
  414.     /* The two aggregates must range over the same variables */
  415.     if ((agg1->sym.value.sym_root.lvarm | agg1->sym.value.sym_root.rvarm) != (aghead2->sym.value.sym_root.lvarm | aghead2->sym.value.sym_root.rvarm))
  416.         ok = FALSE;
  417.  
  418.  
  419.     /* check the qualifications */
  420.     if (ok)
  421.         ok = sameafcn(agg1->right, aghead2->right);
  422.     return (ok);
  423. }
  424.  
  425.  
  426. sameagg(aghead, newaop, agg_depth)
  427. QTREE    *aghead;
  428. QTREE    *newaop;
  429. int    agg_depth;
  430. {
  431.     register QTREE    *agg, *newa;
  432.     register int    i;
  433.  
  434.     agg = aghead;
  435.     newa = newaop;
  436.     agg = agg->left;
  437.     if (agg->sym.type == BYHEAD)
  438.         agg = agg->right;
  439.  
  440.     /* agg now points to first aggregate */
  441.     for (i = 1; agg; agg = agg->left, i++)
  442.         if (sameafcn(agg->right, newa->right) && agg->sym.value.sym_resdom.resno == newa->sym.value.sym_op.opno)
  443.         {
  444. #            ifdef xDTR1
  445.             if (tTf(40, 6))
  446.                 printf("found identical aop %x\n", newa);
  447. #            endif
  448.             return (agg_depth - i);
  449.         }
  450.  
  451.     /* no match */
  452.     return (-1);
  453. }
  454.  
  455.  
  456.  
  457.  
  458. opt_bylist(alist, root)
  459. struct agglist    *alist;
  460. QTREE        *root;
  461. {
  462.     register struct agglist    *al;
  463.     register QTREE        *agg;
  464.     register struct hitlist    *hl;
  465.     QTREE            **tpr, *tree, *lnodv[MAXDOM+2];
  466.     struct hitlist        hlist[30];
  467.     int            anyop, i, usedmap, vars, treemap;
  468.  
  469.     /* compute bitmap of all possible vars in tree (can include xtra vars) */
  470.     treemap = root->sym.value.sym_root.lvarm | root->sym.value.sym_root.rvarm;
  471.     anyop = FALSE;
  472.  
  473.     /* scan the list of aggregates looking for one nested in root */
  474.     for (al = alist; (agg = al->agpoint) && agg != root; al++)
  475.     {
  476.         if (agg->sym.type == AGHEAD && agg->left->sym.type == BYHEAD &&
  477.                 al->agfather == root)
  478.         {
  479.  
  480.             /* this aggregate function is nested in root */
  481.  
  482.             /* make sure it has some vars of interest */
  483.             if ((treemap & varfind(agg->left->left, (QTREE *)NULL)) == 0)
  484.                 continue;
  485.  
  486. #            ifdef xDTR1
  487.             if (tTf(40, 11))
  488.             {
  489.                 printf("nested agg\n");
  490.                 treepr(agg);
  491.             }
  492. #            endif
  493.  
  494.             /* form list of bydomains */
  495.             lnodv[lnode(agg->left->left, lnodv, 0)] = 0;
  496.             usedmap = 0;
  497.  
  498.             De.de_hnext = &hlist[0];
  499.             De.de_hlimit = &hlist[30];
  500.  
  501.             /* find all possible replacements */
  502.             vars = modtree(&root, lnodv, &usedmap);
  503.  
  504.             /*
  505.             ** All references to a variable must be replaced
  506.             ** in order to use this aggregates by-domains.
  507.             */
  508.             if (usedmap && ((vars & usedmap) == 0))
  509.             {
  510. #                ifdef xDTR1
  511.                 if (tTf(40, 7))
  512.                     printf("Committed\n");
  513. #                endif
  514.                 /* success. Committ the tree changes */
  515.                 De.de_hnext->trepr = NULL;
  516.  
  517.                 for (hl = &hlist[0]; tpr = hl->trepr; hl++)
  518.                 {
  519.                     /* get bydomain number */
  520.                     i = hl->byno;
  521.  
  522.                     /* get node being replaced */
  523.                     tree = *tpr;
  524.  
  525.                     /* if it is already a var, just change it */
  526.                     if (tree->sym.type == VAR)
  527.                     {
  528.                         tree->sym.value.sym_var.varno = al->agvarno;
  529.                         tree->sym.value.sym_var.attno = i + 2;
  530.                     }
  531.                     else
  532.                         *tpr = makavar(lnodv[i], al->agvarno, i + 2);
  533.  
  534.                     anyop = TRUE;
  535. #                    ifdef xDTR1
  536.                     if (tTf(40, 7))
  537.                     {
  538.                         printf("modified tree\n");
  539.                         treepr(*tpr);
  540.                     }
  541. #                    endif
  542.                 }
  543.             }
  544.             /* vars is now a map of the variables in the root */
  545.             treemap = vars;
  546.         }
  547.     }
  548.  
  549.     /* if any changes were made, get rid of the unnecessary links */
  550.     if (anyop)
  551.         chklink(root);
  552. }
  553.  
  554.  
  555.  
  556.  
  557. modtree(pnode, lnodv, replmap)
  558. QTREE    **pnode;
  559. QTREE    *lnodv[];
  560. int    *replmap;
  561. {
  562.     register QTREE    *tree;
  563.     register int    vars, i;
  564.     QTREE        *afcn;
  565.  
  566.     /* point up current node */
  567.     if ((tree = *pnode) == NULL)
  568.         return (0);
  569.  
  570.     /* examine each by-list for match on this subtree */
  571.     for (i = 0; afcn = lnodv[i]; i++)
  572.     {
  573.         if (sameafcn(tree, afcn->right))
  574.         {
  575. #            ifdef xDTR1
  576.             if (tTf(40, 9))
  577.             {
  578.                 printf("potential Jackpot");
  579.                 treepr(tree);
  580.             }
  581. #            endif
  582.             vars = varfind(tree, (QTREE *)NULL);
  583.             if (De.de_hnext == De.de_hlimit)
  584.                 return (vars);    /* no more room */
  585.  
  586.             /* record what needs to be done */
  587.             De.de_hnext->trepr = pnode;
  588.             De.de_hnext->byno = i;
  589.             De.de_hnext++;
  590.             *replmap |= vars;
  591.             return (0);
  592.         }
  593.     }
  594.     if (tree->sym.type == VAR)
  595.         return (01 << tree->sym.value.sym_var.varno);
  596.  
  597.     /* try the subtrees */
  598.     vars = modtree(&(tree->left), lnodv, replmap);
  599.     if ((vars & *replmap) == 0)
  600.         vars |= modtree(&(tree->right), lnodv, replmap);
  601.  
  602.     return (vars);
  603. }
  604.  
  605.  
  606. chklink(root)
  607. QTREE    *root;
  608. {
  609.     register QTREE    *r, *b, *last;
  610.  
  611.     last = root;
  612.  
  613.     for (r = last->right; r->sym.type != QLEND; r = r->right)
  614.     {
  615.         /* if this is an EQ node then check for an unnecessary compare */
  616.         if ((b = r->left)->sym.type == BOP && b->sym.value.sym_op.opno == opEQ)
  617.         {
  618.             if (sameafcn(b->left, b->right))
  619.             {
  620. #                ifdef xDTR1
  621.                 if (tTf(40, 5))
  622.                 {
  623.                     printf("unnec clause\n");
  624.                     treepr(b);
  625.                 }
  626. #                endif
  627.                 last->right = r->right;
  628.                 continue;
  629.             }
  630.         }
  631.         last = r;
  632.     }
  633. }
  634.  
  635.  
  636.  
  637. sameafcn(q1, q2)
  638. QTREE *q1, *q2;
  639. {
  640.  
  641.     register QTREE    *t1, *t2;
  642.     register int    len;
  643.     int        type;
  644.  
  645.     t1 = q1;
  646.     t2 = q2;
  647.  
  648.     if (!(t1 && t2)) 
  649.         return(!(t1 || t2));
  650.     len = (t1->sym.len & I1MASK) + SYM_HDR_SIZ;
  651.     type = t1->sym.type;
  652.     if (type == VAR)
  653.         len = sizeof(struct varnode);
  654.     if (type == AND)
  655.         len = 2;
  656.     if (!bequal(&t1->sym.type, &t2->sym.type, len)) 
  657.         return(0);
  658.     return(sameafcn(t1->left,t2->left) && sameafcn(t1->right,t2->right));
  659. }
  660. /*
  661. **    varfind -- find all variables in the tree pointed to by "root".
  662. **        Examine all parts of the tree except aggregates. For
  663. **        aggregates, ignore simple aggregate and look only
  664. **        at the by-lists of aggregate functions. If the aggregate
  665. **        is "aghead" then ignore it. There is no reason to look
  666. **        at yourself!!!!
  667. **        This routine is called by byeval() to determine
  668. **        whether to link the aggregate to the root tree.
  669. **
  670. **    Curiosity note: since the tree being examined has not been
  671. **    processed by decomp yet, ckvar does not need to be called
  672. **    since the var could not have been altered.
  673. */
  674.  
  675. varfind(root, aghead)
  676. QTREE    *root;
  677. QTREE    *aghead;
  678. {
  679.     register QTREE    *tree;
  680.     register int    type;
  681.  
  682.     if ((tree = root) == NULL)
  683.         return (0);
  684.  
  685.     if ((type = tree->sym.type) == AGHEAD)
  686.     {
  687.         /* ignore if it matches aghead */
  688.         if (tree == aghead)
  689.             return (0);
  690.         /* if this is an aggregate function, look at bylist */
  691.         tree = tree->left;
  692.         if ((type = tree->sym.type) != BYHEAD)
  693.             return (0);
  694.     }
  695.  
  696.     if (type == VAR)
  697.         return (1 << tree->sym.value.sym_var.varno);
  698.  
  699.     return (varfind(tree->left, aghead) | varfind(tree->right, aghead));
  700. }
  701.